/**
 * 72. Edit Distance 编辑距离
 * https://leetcode-cn.com/problems/edit-distance/
 */
class EditDistance {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();

        // 使用一维数组优化空间复杂度
        int[] dp = new int[n + 1];

        // 初始化第一行（空字符串转换为word2前j个字符的编辑距离）
        for (int j = 0; j <= n; j++) {
            dp[j] = j;
        }

        for (int i = 1; i <= m; i++) {
            // 保存左上角的值（相当于dp[i-1][j-1]）
            int pre = dp[0];
            // 初始化当前行的第一个值（相当于dp[i][0]）
            dp[0] = i;

            for (int j = 1; j <= n; j++) {
                // 保存当前值，作为下一次迭代的pre
                int temp = dp[j];

                if (word1.charAt(i-1) == word2.charAt(j-1)) {
                    dp[j] = pre;  // 字符相同，无需操作
                } else {
                    // 取插入、删除、替换操作的最小值
                    dp[j] = Math.min(Math.min(dp[j-1], dp[j]), pre) + 1;
                }

                pre = temp;  // 更新pre为当前格的旧值
            }
        }

        return dp[n];
    }
}